/*

方法1：
时间复杂度：O(N)
空间复杂度：O(N)

case1:

r:

*/
package medium

import "math"

func mincostTickets(days []int, costs []int) int {
	n := len(days)
	minDay, maxDay := days[0], days[n-1]
	dp := make([]int, maxDay+31)
	for d, i := maxDay, n-1; d >= minDay; d-- {
		if d == days[i] {
			dp[d] = min(dp[d+1]+costs[0], dp[d+7]+costs[1], dp[d+30]+costs[2])
			i--
		} else {
			dp[d] = dp[d+1]
		}
	}
	return dp[minDay]
}

func min(arr ...int) int {
	if len(arr) == 0 {
		return math.MaxInt32
	}
	result := math.MaxInt32
	for _, v := range arr {
		if result > v {
			result = v
		}
	}
	return result
}
